//
// Created by ASUS on 2024/6/3/星期一.
//
#include <bits/stdc++.h>
using namespace std;

class MinHeap {
private:
    vector<int> heap;
public:
    MinHeap() = default;
    void insert(int x) {
        heap.push_back(x);
        int i = (int)heap.size() - 1;
        while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
            swap(heap[(i - 1) / 2], heap[i]);
            i = (i - 1) / 2;
        }
    }
    int extractMin() {
        if (heap.empty()) return -1;
        int min = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        int i = 0;
        while (i < (int)heap.size()) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int minIndex = i;
            if (left < (int)heap.size() && heap[left] < heap[minIndex]) minIndex = left;
            if (right < (int)heap.size() && heap[right] < heap[minIndex]) minIndex = right;
            if (minIndex == i) break;
            swap(heap[i], heap[minIndex]);
            i = minIndex;
        }
        return min;
    }
    int getSize() {
        return (int)heap.size();
    }
    bool isEmpty() {
        return heap.empty();
    }
};

int main() {
    MinHeap heap;
    heap.insert(3);
    heap.insert(2);
    heap.insert(1);
    heap.insert(4);
    heap.insert(5);
    while (!heap.isEmpty()) {
        cout << heap.extractMin() << " ";
    }
    cout << endl;
    return 0;
}